package cn.mayday.algorithms.year2021.month1.动态规划或者贪心;

/**
 * 剑指 Offer 14- I. 剪绳子
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 * <p>
 * 示例 1：
 * <p>
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1
 * <p>
 * 和Leetcode 343相同 【中等难度】
 * <p>
 * 示例 2:
 * <p>
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
 * <p>
 * 343. 整数拆分
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 *
 * @author Mayday05
 * @date 2021/5/13 11:07
 */
public class Offer014ICuttingRope {


    public static void main(String[] args) {
        new Offer014ICuttingRope().cuttingRope(6);
    }

    // 动态规划 ： 【中等难度】
    // 关键思想：假设在j出分隔后，dp[i]的结果为固定j处裁剪后，乘以后者，是i-j是继续裁剪更大，还是不裁剪更大。
    // 即dp[i] = Math.max(j * (i - j), j * dp[i - j]); (注意，这里略有变化，由于j是遍历)


    // 步骤一：状态模型的定义，初始化条件
    // 步骤二：状态转移方程，即递推

    public int cuttingRope(int n) {

        // 定义状态， dp[i]状态表示i长度时至少裁剪一刀的最大值（注意是至少在裁剪一刀）
        int[] dp = new int[n + 1]; // 注意这里为什么是n+1，因为定义的数组是想让返回dp[n]表示n的结果，所以
        // 定义初始化
        dp[0] = 0;
        dp[1] = 0;


        // 循环遍历，计算dp[i]
        for (int i = 2; i <= n; i++) {
            int max = 0; // 定义j轮训的最大值临时变量

            // 假设在j处分隔了一刀，由于至少分割一刀，因此j<i,即从最左边和最右边看都至少保留一位
            for (int j = 1; j < i; j++) {
                // [关键：状态转移方程]比较j处分割时，左边循环固定，右边是继续裁剪更大，还是不裁剪更大
                int temp = Math.max(j * (i - j), j * dp[i - j]);
                max = Math.max(temp, max); // 更新最大值
            }

            dp[i] = max; // 赋值dp[i]
        }

        return dp[n];
    }


}
